package com.hare.harelearn.DataStructure.ArrayAlgorithm;

/**
 * @program: HareLearn
 * @description:
 * @author: Hare
 * @create: 2025−03-09 23:29
 * @Version 1.0
 **/
public class 搜索插入位置 {

    public static void main(String[] args) {
        //System.out.println(searchInsert(new int[]{2,3,4,7,8,9}, 11));
        System.out.println(searchInsert(new int[]{1, 3, 5, 6,7,10,23,45,56}, 46));
        //System.out.println(searchInsert(new int[]{1,3,5,6}, 0));
    }


    /**
     * 折半查找
     * 直接折半查找就ok，返回left
     * @param nums
     * @param target
     * @return
     */
    public static int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) >>> 1;
            if(target == nums[mid]){
                return mid;
            }
            if(nums[mid] > target){
                right = mid  - 1;
            }
            if(nums[mid] < target){
                left = mid + 1;
            }
        }
        return left;
    }
}
